

# 层序遍历

class Solution:

    def levelOrder(self, root):
        if not root:
            return []

        q = []

        q.append(root)

        ans = []
        while q:
            
            tmp = []
            for _ in range(len(q)):

                it = q.pop(0)
                if it:
                    tmp.append(it.val)
                    q.append(it.left)
                    q.append(it.right)
            if tmp:
                ans.append(tmp)

        return ans


